package com.cdy.demo.algorithm;

public class Leetcode1049 {

	public static void main(String[] args) {
		Leetcode1049 Leetcode5 = new Leetcode1049();
		Leetcode5.lastStoneWeightII(new int[]{31, 26, 33, 21, 40});


	}

	public int lastStoneWeightII(int[] stones) {

		int len = stones.length;
		int sum = 0;
		for (int stone : stones) {
			sum += stone;
		}
		int[][] dp = new int[len + 1][sum / 2 + 1];

		for (int i = 0; i < len + 1; i++) {
			for (int j = 0; j < (sum / 2 + 1); j++) {
				if (i == 0) {
					dp[i][j] = 0;
				} else if (j == 0) {
					dp[i][j] = 0;
				} else if (j >= stones[i-1]) {
					dp[i][j] = Math.max(dp[i - 1][j], dp[i-1][j - stones[i-1]] + stones[i-1]);
				} else {
					dp[i][j] = dp[i - 1][j];
				}
			}
		}
		return Math.abs(sum - dp[len][sum / 2]- dp[len][sum / 2]);
	}
}
